package 我的Java学习_算法基础.day_02;

import static 我的Java学习_算法基础.day_01.唯一成对的数.printArray;

public class 传统插入排序 {
    public static void main(String[] args) {
        int[] a = {9,6,4,3,3};
        int[] b = {9,6,4,3,3};
        sort(a);
        traditionInsertSort(b);
        printArray(a);
        printArray(b);
    }
    static void sort(int[] array){
        for(int interval = array.length/2;interval>0;interval/=2){
            //增量为1
            for(int i =1;i< array.length;i++){
                int target=array[i];
                int j =i-1;
                while(j>-1&&target<array[j]){
                    array[j+1]=array[j];
                    j--;
                }
                array[j+1]=target;
            }
        }
    }
    public static  void traditionInsertSort(int[] array){
        traditionInsertSort1(array,0,array.length-1);
    }
    /**
     *
     * @param array 要排序的数组
     * @param low 要排序的第一个元素下标
     * @param high 要排序的最后一个元素下标
     */
    static void traditionInsertSort1(int[] array,int low,int high){
        for(int i = low +1;i<=high;i++){
            int k = array[i];
            int j = i -1;
            while(j>=low&&array[j]>k){
                array[j+1]=array[j];
                j--;
            }
            array[j+1] = k;
        }
    }

}
